package com.loop.binarySearch;

public class Test {
    public static void main(String[] args) {
        int[] arr = {-1,0,1,3,5,7,9,10,11};
        System.out.println(binarySearch(arr,4));
    }

    /**
     * 有序（升序）数组的二分查找，返回值要是为-1表示数组元素未查找到
     * @param arr 有序的int类型的数组
     * @param num 需要找到的元素内容
     * @return 返回此元素在数组中的下标
     */
    public static int binarySearch(int[] arr,int num){
        if (arr.length<1 || arr==null){
            return -1;
        }
        int beforeIndex=0;
        int afterIndex=arr.length-1;
        //因为是有序数组，如果比最大值大或者比最小值小，就没有必要进行搜查了
        if (num < arr[beforeIndex] || num > arr[afterIndex]){
            return -1;
        }
        for (;;){
            //当前下标与后下标相等或者相邻时，表示未查找到
            if (beforeIndex+1>=afterIndex){
                return -1;
            }
            //中间下标
            int midIndex = (beforeIndex+afterIndex)/2;
            if (num>arr[midIndex]){
                //若num比中间下标值大的话，就将中间下标赋值给前下标
                beforeIndex = midIndex;
            }else if (num<arr[midIndex]){
                //若num比中间下标值小的话，就将中间下标赋值给后下标
                afterIndex = midIndex;
            }else {
                return midIndex;
            }
        }
    }
}
